#define DS

#include <iostream>
#include <vector>
#include <string>
#include <queue>
using namespace std;

// 二叉树
class TreeNode
{
public:
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int val) : val(val), left(nullptr), right(nullptr) {}
    // 层次遍历序列 反序列化 二叉树
    TreeNode(const string& str)
    {
        if (str.size() == 0)
            return;

        vector<char> arr;
        int pos = 0;
        while ((pos = str.find('_', pos)) != string::npos)
        {
            arr.push_back(str[pos - 1]);
            ++pos;
        }

        queue<TreeNode*> q;
        int index = 0;
        this->val = arr[index] - '0';
        index += 1;
        q.push(this);
        TreeNode* cur;
        while (!q.empty())
        {
            cur = q.front();
            q.pop();
            cur->left = arr[index] == '#' ? nullptr : new TreeNode(arr[index] - '0');
            cur->right = arr[index + 1] == '#' ? nullptr : new TreeNode(arr[index + 1] - '0');
            index += 2;

            if (cur->left)
                q.push(cur->left);

            if (cur->right)
                q.push(cur->right);
        }
    }
};

// 单链表
class ListNode
{
public:
    int val;
    ListNode* next;

    ListNode() : val(0), next(nullptr) {}
    ListNode(int val) : val(val), next(nullptr) {}
};